package middle;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.longestPalindrome("babad");
    }
    /**
     * 中心扩散法
     * 回文串如abcba
     * 我们可以将其中一个元素作为中心，往左右扩散，然后得出最长的回文子串的长度，比如上述回文子串中，c作为中心扩散出来的回文子串最长
     * 对于长度为偶数的回文串 比如abccba 那么我们应当从cc中间开始向两边扩散。所以中心位置的不仅仅是具体的元素位置，还应当包含元素中间的位置。
     * 故 中心位置的数量为n+(n-1)  n为字符串的长度
     *
     * 参考链接 https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/
     * */
    static class Solution {
        public String longestPalindrome(String s) {
            int start=0, end=0;
            for (int i=0; i<s.length(); i++){
                int l1 = diffusionCenter(s, i, i);
                int l2 = diffusionCenter(s, i, i+1);
                int len = Math.max(l1, l2);
                if(len > (end - start + 1)){
                    start = i - (len-1)/2;
                    end = i + len/2;
                }
            }
            return s.substring(start, end + 1);
        }

        int diffusionCenter(String s, int left, int right){
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            return right-left-1;
        }
    }
}
